/// @tags: OptimizeBuildingEdges Prefix Suffix Dij VirtualTree Trie
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define rint register int

using std::cin;
using std::cout;

namespace BlueQuantum {

constexpr int maxn = 100, maxe = 5e2 + 3, inf = 0x3f3f3f3f, maxlog = 18;

enum Type { IN, OUT, NONE };

struct ENode {
  int eid, tid, typ;
};

namespace Trie {

constexpr int maxe = 2e2 + 3;

int ecnt, dcnt, stcnt;
int heads[maxn], dfn[maxn], dep[maxn];

struct Edge {
  int v, nxt;
} e[maxe];

inline void add(int u, int v) { e[++ecnt].v = v, e[ecnt].nxt = heads[u], heads[u] = ecnt; }

std::vector<ENode> key;
int lg[maxn * 2], st[maxlog][maxn * 2];

void dfs(int u) {
  dfn[u] = ++dcnt;
  st[0][dcnt] = u;
  for (int i = heads[u]; i; i = e[i].nxt) {
    dep[e[i].v] = dep[u] + 1;
    dfs(e[i].v);
    st[0][++dcnt] = u;
  }
}

inline void sort() {
  std::sort(key.begin(), key.end(),
            [](const ENode &lhs, const ENode &rhs) { return dfn[lhs.tid] < dfn[rhs.tid]; });
}

inline int cmp(int x, int y) { return dep[x] < dep[y] ? x : y; }

inline void prework() {
  for (int i = 2; i <= dcnt; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i < maxlog; ++i) {
    for (int j = 1; j + (1 << i) - 1 <= dcnt; ++j) {
      st[i][j] = cmp(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
    }
  }
}

inline int getLca(int x, int y) {
  x = dfn[x], y = dfn[y];
  if (x > y) std::swap(x, y);
  int k = lg[y - x + 1];
  cout << "lca: " << cmp(st[k][x], st[k][y - (1 << k) + 1]) << '\n';
  return cmp(st[k][x], st[k][y - (1 << k) + 1]);
}

inline void buildV(int &cnt) {
  sort();
  for (int i = 1; i < cnt; ++i) {
    key.push_back(ENode{0, getLca(key[i].tid, key[i - 1].tid), NONE});
  }
  sort();
  cnt = key.size();
}

inline void clear() {
  ecnt = 0;
  memset(heads, 0, sizeof(heads));
}

}  // namespace Trie
using Trie::dep;
using Trie::key;

struct Edge {
  int v, nxt, w;
} e[maxe];

int ecnt, ncnt;
int heads[maxn], ein[maxe], eout[maxe], preIn[maxn], preOut[maxn], sufIn[maxn], sufOut[maxn];
int dis[maxe * 8];

inline void add(int u, int v, int w) {
  e[++ecnt].v = v, e[ecnt].nxt = heads[u], heads[u] = ecnt, e[ecnt].w = w;
}

struct Node {
  int u, d;
  inline bool operator<(const Node &rhs) const { return d > rhs.d; }
};

std::vector<ENode> in[maxn], out[maxn];

inline void dij(int s) {
  static std::priority_queue<Node> pq;
  memset(dis, 0x3f, sizeof(dis));
  for (auto &v : out[s]) {
    dis[v.eid] = 0;
    pq.push(Node{v.eid, 0});
  }
  while (!pq.empty()) {
    int u = pq.top().u, d = pq.top().d;
    pq.pop();
    if (d != dis[u]) continue;
    for (int i = heads[u]; i; i = e[i].nxt) {
      int v = e[i].v;
      if (dis[v] > dis[u] + e[i].w) {
        dis[v] = dis[u] + e[i].w;
        pq.push(Node{v, dis[v]});
      }
    }
  }
}

inline void buildEdge(int x) {
  int cnt = 0;
  for (auto &v : in[x]) key.push_back(v), ++cnt;
  for (auto &v : out[x]) key.push_back(v), ++cnt;
  Trie::buildV(cnt);
  for (int i = 0; i < cnt; ++i) {
    preIn[i] = ++ncnt, preOut[i] = ++ncnt;
    sufIn[i] = ++ncnt, sufOut[i] = ++ncnt;
  }
  for (int i = 1; i < cnt; ++i) {
    add(preIn[i - 1], preIn[i], 0);
    add(preOut[i - 1], preOut[i], 0);
  }
  for (int i = 1; i < cnt; ++i) {
    add(sufIn[i], sufIn[i - 1], 0);
    add(sufOut[i], sufOut[i - 1], 0);
  }
  for (int i = 0; i < cnt; ++i) {
    switch (key[i].typ) {
      case IN: {
        add(key[i].eid, preIn[i], 0);
        add(key[i].eid, sufIn[i], 0);
      } break;
      case OUT: {
        add(preOut[i], key[i].eid, 0);
        add(sufOut[i], key[i].eid, 0);
      } break;
    }
  }
  for (int i = 0; i < cnt; ++i) {
    add(preIn[i], preOut[i], dep[key[i].tid]);
    add(sufIn[i], sufOut[i], dep[key[i].tid]);
  }
  key.clear();
}

inline int main() {
  int t;
  cin >> t;
  while (t--) {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= m; ++i) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      ein[i] = ++ncnt;
      eout[i] = ++ncnt;
      in[b].push_back(ENode{eout[i], d, IN});
      out[a].push_back(ENode{ein[i], d, OUT});
      add(ein[i], eout[i], c);
    }
    for (int i = 1; i < k; ++i) {
      int u, v, w;
      cin >> u >> v >> w;
      Trie::add(u, v);
    }

    Trie::dfs(1);
    Trie::prework();
    for (int i = 1; i <= n; ++i) {
      buildEdge(i);
    }

    dij(1);
    // print answer
    for (int i = 2; i <= n; ++i) {
      int ans = inf;
      for (auto &v : in[i]) {
        ans = std::min(ans, dis[v.eid]);
      }
      cout << ans << '\n';
    }

    // clear
    ncnt = ecnt = 0;
    for (int i = 1; i <= n; ++i) {
      in[i].clear();
      out[i].clear();
    }
    Trie::clear();
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("CppTest.in", "r", stdin);
  freopen("CppTest.out", "w", stdout);
#endif
#endif

  std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
  return BlueQuantum::main();
}
